"""
模拟退火算法求解旅行商问题（TSP）

问题描述：
    给定一系列城市和每对城市之间的距离，寻找访问每个城市一次且仅一次，
    最后返回起点的最短路径。
    
算法原理：
    模拟退火算法是一种启发式搜索算法，灵感来源于固体物质的退火过程。
    它从一个随机初始解开始，在每次迭代中随机生成一个新的邻近解。
    如果新解优于当前解，则接受新解。如果新解劣于当前解，则以一定概率接受新解，
    该概率随温度的降低而减小。这种机制使得算法在搜索初期能够跳出局部最优，
    在搜索后期则趋于收敛到全局最优。

核心概念：
    - 温度（Temperature）：控制接受劣解的概率，随迭代次数逐渐降低。
    - 冷却速率（Cooling Rate）：温度下降的速度。
    - 邻域搜索：通过交换两个城市的位置来生成新解。
    
应用场景：
    模拟退火算法适用于解决各种组合优化问题，例如：
    - 旅行商问题（TSP）
    - 背包问题
    - 调度问题
    - VLSI设计
    - 图像处理

作者：斯黄
日期：2025年3月4日
"""

import numpy as np
import matplotlib.pyplot as plt
import random
import math

# 城市坐标数据
cities = np.array([
    (116.4074, 39.9042),  # 北京
    (121.4737, 31.2304),  # 上海
    (113.2644, 23.1291),  # 广州
    (114.0579, 22.5431),  # 深圳
    (104.0668, 30.6706)   # 成都
])
NUM_CITIES = len(cities)

# 计算路径总距离
def calculate_distance(path):
    total_distance = 0
    for i in range(len(path)):
        city_a = path[i]
        city_b = path[(i + 1) % len(path)]
        total_distance += np.linalg.norm(cities[city_a] - cities[city_b])
    return total_distance

# 生成初始解
def generate_initial_solution(num_cities):
    path = list(range(num_cities))
    random.shuffle(path)
    return path

# 生成邻近解（交换两个城市）
def get_neighbor(path):
    new_path = path[:]
    idx1, idx2 = random.sample(range(len(new_path)), 2)
    new_path[idx1], new_path[idx2] = new_path[idx2], new_path[idx1]
    return new_path

# 模拟退火主程序
def simulated_annealing(initial_solution, initial_temperature, cooling_rate, max_iterations):
    current_solution = initial_solution
    current_distance = calculate_distance(current_solution)
    
    best_solution = current_solution
    best_distance = current_distance
    
    temperature = initial_temperature
    
    history_distances = []

    for i in range(max_iterations):
        neighbor_solution = get_neighbor(current_solution)
        neighbor_distance = calculate_distance(neighbor_solution)
        
        # 计算能量差
        delta_E = neighbor_distance - current_distance
        
        # 判断是否接受新解
        if delta_E < 0 or random.random() < math.exp(-delta_E / temperature):
            current_solution = neighbor_solution
            current_distance = neighbor_distance
        
        # 更新最优解
        if current_distance < best_distance:
            best_solution = current_solution
            best_distance = current_distance
        
        # 降温
        temperature *= cooling_rate
        
        history_distances.append(best_distance)

    return best_solution, best_distance, history_distances

# 可视化函数
def visualize_tsp(path, distance, generation_history):
    plt.figure(figsize=(12, 6))

    # 绘制路径图
    plt.subplot(1, 2, 1)
    path_coords = cities[path + [path[0]]] # 闭合路径
    plt.plot(path_coords[:, 0], path_coords[:, 1], 'r-o', label=f'Best Path (Distance: {distance:.2f})')
    plt.scatter(cities[:, 0], cities[:, 1], c='blue', label='Cities')
    for i, (x, y) in enumerate(cities):
        plt.text(x, y, str(i), fontsize=12, ha='right')
    plt.title('TSP Solution by Simulated Annealing')
    plt.xlabel('Longitude')
    plt.ylabel('Latitude')
    plt.legend()
    plt.grid(True)

    # 绘制收敛曲线
    plt.subplot(1, 2, 2)
    plt.plot(generation_history, color='blue')
    plt.title('Convergence of Best Distance')
    plt.xlabel('Iteration')
    plt.ylabel('Best Distance')
    plt.grid(True)

    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    # 参数设置
    initial_temperature = 10000
    cooling_rate = 0.99
    max_iterations = 10000

    initial_solution = generate_initial_solution(NUM_CITIES)
    best_path, min_distance, history = simulated_annealing(initial_solution, initial_temperature, cooling_rate, max_iterations)

    print(f"最终最短路径: {best_path}")
    print(f"最终最短距离: {min_distance:.2f}")

    visualize_tsp(best_path, min_distance, history) 